package beusoft.ccjk.com.calculator.sort;

/**
 * Created by CCJK on 2017/12/24.
 */

public class QuickSort {

    public static void sort(int arr[]) {

        recQuickSort(arr, 0, arr.length - 1);
    }

    /**
     * 这是粗略版的快速排序，直接以最右端的元素为划分点，但是这样对越
     * 全倒着排列的数组没有效率，可以换成三数据项取中，小于或等于三个的元素直接用插入排序，效率更高
     *
     * @param arr
     * @param left
     * @param right
     */
    private static void recQuickSort(int arr[], int left, int right) {
        if (left >= right) {
            return;
        } else {
            //划分点
            long pivot = arr[right];
            int partition = partitionIt(arr, left, right, pivot);
            recQuickSort(arr, left, partition - 1);
            recQuickSort(arr, partition + 1, right);
        }

    }

    private static int partitionIt(int arr[], int left, int right, long pivot) {
        int leftPtr = left - 1;
        int rightPtr = right + 1;
        while (true) {
            while (arr[++leftPtr] < pivot) ;
            while (rightPtr > 0 && arr[--right] > pivot) ;
            if (leftPtr >= rightPtr) break;
            else
                swap(arr, leftPtr, rightPtr);
        }
        //已经找到了right位置的元素的确定位置就是leftPtr,可以节省排序时间
        //recQuickSort(arr, left, partition - 1);
        //   recQuickSort(arr, partition + 1, right);
        //这里没有对划分点进行排序，其实就是这个原因
        swap(arr, leftPtr, right);
        return leftPtr;
    }

    private static void swap(int arr[], int leftPtr, int rightPtr) {
        int temp = arr[leftPtr];
        arr[leftPtr] = arr[rightPtr];
        arr[rightPtr] = temp;
    }

}
